<?php
// 力扣 131. 分割回文串

class Solution
{

    /**
     * @param String $s
     * @return String[][]
     */
    function partition($s)
    {
        //深度优先遍历
        $sLen = strlen($s);
        if ($sLen == 0)//递归结束
            return [];

        $ret = [];//保存返回结果
        for ($i = 1; $i <= $sLen; $i++) {
            $subStr = substr($s, 0, $i);
            if ($this->isPartition($subStr)) {
                $subArr = $this->partition(substr($s, $i, $sLen - $i));//回溯
                foreach ($subArr as $v) {
                    array_unshift($v, $subStr);
                    $ret[] = $v;//符合条件存入
                }
                if (empty($subArr)) {//递归到底返回
                    $ret[] = [$subStr];//符合条件存入，因为前面已经判断过是回文串
                }
            }
        }

        return $ret;
    }

    //判断字符串是否是回文串
    function isPartition($s)
    {
        $sLen = strlen($s);
        $l = 0;
        $r = $sLen - 1;
        while ($l < $r) {
            if ($s[$l] != $s[$r])
                return false;
            $l++;
            $r--;
        }
        return true;
    }

}

$solution = new Solution();
$s = "aab";
$res = $solution->partition($s);
print_r($res);